Improved quantum backtracking algorithms through effective resistance estimates

摘要

We investigate quantum backtracking algorithms of a type previouslyintroduced by Montanaro (arXiv:1509.02374). These algorithms explore trees ofunknown structure, and in certain cases exponentially outperform classicalprocedures (such as DPLL). Some of the previous work focused on obtaining aquantum advantage for trees in which a unique marked vertex is promised toexist. We remove this restriction and re-characterise the problem in terms ofthe effective resistance of the search space. To this end, we present ageneralisation of one of Montanaro's algorithms to trees containing $k \geq 1$marked vertices, where $k$ is not necessarily known \textit{a priori}. Our approach involves using amplitude estimation to determine a near-optimalweighting of a diffusion operator, which can then be applied to prepare asuperposition state that has support only on marked vertices and ancestorsthereof. By repeatedly sampling this state and updating the input vertex, amarked vertex is reached in a logarithmic number of steps. The algorithmthereby achieves the conjectured bound of$\widetilde{\mathcal{O}}(\sqrt{TR_{\mathrm{max}}})$ for finding a single markedvertex and $\widetilde{\mathcal{O}}\left(k\sqrt{T R_{\mathrm{max}}}\right)$ forfinding all $k$ marked vertices, where $T$ is an upper bound on the tree sizeand $R_{\mathrm{max}}$ is the maximum effective resistance encountered by thealgorithm. This constitutes a speedup over Montanaro's original procedure inboth the case of finding one and finding multiple marked vertices in anarbitrary tree. If there are no marked vertices, the effective resistancebecomes infinite, and we recover the scaling of Montanaro's existencealgorithm.